1. Technical Field
The present invention generally relates to multi-node communication systems with shared resources. More particularly, the present invention relates to allocation of shared resource access quota in multi-node communication systems.
2. Background Art
In the past, multi-node communication systems, such as local area networks, including both ring networks and bus networks, have attempted to manage node access to shared resources by setting a predetermined limit on the amount of resources allocated to any one node. Although several different mechanisms exist to accomplish this, including polling, random access, time slot and quota allocation mechanisms, the present invention will focus on quota allocation mechanisms.
Once a node has exhausted its quota, existing quota allocation schemes generally do not allow it to transmit again until all the other nodes have exhausted their quota, at which time the quotas are refreshed. While such a quota scheme guarantees an equitable access to the shared resources, the fixed quota size may lead to either underutilization of the system or to long access delays. If the fixed quota is too small, the system may be underutilized since the nodes may deplete their quota while waiting for the quota refresh signal to propagate through the system. Thus, nodes may be idle for an extended time relative to the transmission time. On the other hand, if the fixed quota is too large and the system is heavily loaded by one or a few nodes, some nodes may have a long access delay proportional to the number of active nodes before gaining access to the shared resource. In existing schemes, the fixed quota is set at some level between the two extremes. One such fixed quota allocation scheme is disclosed in U.S. Pat. No. 4,926,418 issued to Cidon et al. and assigned to IBM (hereinafter, "the Cidon patent"), the disclosure of which is herein incorporated by reference in its entirety.
Shared resource access control mechanisms can be either distributed or centralized. A centralized access control mechanism requires a dedicated node to act as the controller for receiving access requests and granting and managing access allocations to the other nodes. A distributed access control mechanism distributes these responsibilities among the nodes and does not require a dedicated node, and is, therefore, less complex than a centralized access control mechanism.
Thus, a need exists for a distributed quota allocation mechanism that can adapt to changing load conditions.